package com.study.homework;

import com.study.sort.SortMain;

import java.util.Arrays;

/**
 * https://time.geekbang.org/column/article/80458
 * <p>
 * 排序
 * 实现归并排序、快速排序、插入排序、冒泡排序、选择排序
 * 编程实现 O(log n) 时间复杂度内找到一组数据的第 K 大元素
 * <p>
 * 二分查找
 * 实现一个有序数组的二分查找算法
 * 实现模糊二分查找算法（比如大于等于给定值的第一个元素）
 * <p>
 * leetcode
 * https://leetcode-cn.com/problems/sqrtx/
 */
public class Day3 {

    public static void main(String[] args) {
        int[] array = SortMain.getInts(10);
        System.out.println(Arrays.toString(array));
        //归并排序
        System.out.println(Arrays.toString(mergeSort(array.clone())));
        //快速排序
        System.out.println(Arrays.toString(quickSort(array.clone())));
        //选择排序
        System.out.println(Arrays.toString(selectedSort(array.clone())));
        //冒泡排序
        System.out.println(Arrays.toString(bubbleSort(array.clone())));
        //插入排序
        System.out.println(Arrays.toString(insetSort(array.clone())));
        //编程实现 O(log n) 时间复杂度内找到一组数据的第 K 大元素
        //1.先排序 再找    快排 => nlogn
        //2. 类似快排 取中值m,小放左 大放右边, 直到m==k, 时间复杂度 O(n)
        System.out.println(findTopK(array, 1));


        int[] a = {1, 2, 5, 6, 6, 7, 8, 10};
        System.out.println(Arrays.toString(a));
        //实现一个有序数组的二分查找算法
        System.out.println(binarySearch(a, 6));

        //实现模糊二分查找算法（比如大于等于给定值的第一个元素）
        System.out.println(findFirstTop(a, 0));

        //69. x 的平方根
//        System.out.println(mySqrt(144));
//        System.out.println(mySqrt(10000));
        System.out.println(mySqrt(25000000));
        System.out.println(mySqrt(2147395600));
    }

    public static int mySqrt(int x) {
        if (x == 0 || x == 1) {
            return x;
        }

        long l = 1;
        long h = (x >> 1) + 1;

        while (l < h) {
            long m = l + ((h - l) >> 1);
            if (m * m > x) {
                h = m - 1;
            } else {
                if ((m + 1) * (m + 1) > x) {
                    return (int)m;
                }
                l = m + 1;

            }
        }
        return (int)l;
    }

    private static int findFirstTop(int[] a, int value) {
        int l = 0;
        int h = a.length - 1;

        while (l <= h) {
            int m = l + ((h - l) >> 1);
            if (a[m] > value) {
                h = m - 1;
            } else if (a[m] < value) {
                l = m + 1;
            } else {
                if (m == 0 || a[m - 1] < value) {
                    return m;
                }
                h = m - 1;
            }
        }
        return -1;

//        return findFirstTop(a, 0, a.length - 1, value);
    }

    private static int findFirstTop(int[] a, int l, int h, int value) {
        if (l > h) {
            return -1;
        }

        int m = l + ((h - l) >> 1);
        if (a[m] >= value) {
            if (m <= 0 || a[m - 1] < value) {
                return m;
            }
            return findFirstTop(a, l, m - 1, value);
        } else {
            return findFirstTop(a, m + 1, h, value);
        }
    }

    private static int binarySearch(int[] a, int value) {
        return binarySearch(a, 0, a.length - 1, value);
    }

    private static int binarySearch(int[] a, int l, int h, int value) {
        if (l >= h) {
            return l;
        }

        int m = l + ((h - l) >> 1);

        if (a[m] > value) {
            m = binarySearch(a, l, m - 1, value);
        } else if (a[m] < value) {
            m = binarySearch(a, m + 1, h, value);
        } else {
            return m;
        }
        return m == -1 ? -1 : a[m] == value ? m : -1;
    }


    /**
     * 第K大元素
     */
    private static int findTopK(int[] a, int k) {
        if (k <= 0 || k > a.length) {
            return -1;
        }

        return a[findTopK(a, 0, a.length - 1, a.length - k)];
//        return findTopK(a, 0, a.length - 1, a.length - k);
    }

    private static int findTopK(int[] a, int l, int h, int k) {
        if (l >= h) {
            return l;
        }
        int m = partition(a, l, h);
        if (m > k) {
            m = findTopK(a, l, m - 1, k);
        } else if (m < k) {
            m = findTopK(a, m + 1, h, k);
        }
        return m;
    }

    private static int partition(int[] a, int l, int h) {
        int value = a[h];

        int p = l;

        for (int i = l; i < h; i++) {
            if (a[i] < value) {
                int temp = a[i];
                a[i] = a[p];
                a[p] = temp;
                p++;
            }
        }

        a[h] = a[p];
        a[p] = value;
        return p;
    }


    private static int[] selectedSort(int[] a) {
        for (int i = 0; i < a.length; i++) {
            int min = i;
            for (int j = i; j < a.length; j++) {
                if (a[j] < a[min]) {
                    min = j;
                }
            }

            int temp = a[min];
            a[min] = a[i];
            a[i] = temp;
        }
        return a;
    }

    private static int[] bubbleSort(int[] a) {
        boolean swap;
        for (int i = 0; i < a.length - 1; i++) {
            swap = false;
            for (int j = 0; j < a.length - i - 1; j++) {
                if (a[j] > a[j + 1]) {
                    int temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                    swap = true;
                }
            }

            if (!swap) {
                return a;
            }
        }
        return a;
    }

    private static int[] insetSort(int[] a) {
        for (int i = 1; i < a.length; i++) {
            for (int j = i; j > 0; j--) {
                if (a[j] < a[j - 1]) {
                    int temp = a[j];
                    a[j] = a[j - 1];
                    a[j - 1] = temp;
                }
            }

//            int p = i;
//            while (p > 0 && a[p] < a[p - 1]) {
//                int temp = a[p];
//                a[p] = a[p - 1];
//                a[p - 1] = temp;
//                p--;
//            }
        }
        return a;
    }

    /**
     * 快速排序
     */
    private static int[] quickSort(int[] a) {
        quickSort(a, 0, a.length - 1);
        return a;
    }

    private static void quickSort(int[] a, int l, int r) {
        if (l >= r) {
            return;
        }
        int m = getMid(a, l, r);
        quickSort(a, l, m - 1);
        quickSort(a, m + 1, r);
    }

    private static int getMid(int[] a, int l, int r) {
        int value = a[r];

        int p = l;
        int temp;
        for (int i = l; i < r; i++) {
            temp = a[i];
            if (temp <= value) {
                a[i] = a[p];
                a[p] = temp;
                p++;
            }
        }

        temp = a[p];
        a[p] = a[r];
        a[r] = temp;
        return p;
    }

    /**
     * 归并排序
     */
    private static int[] mergeSort(int[] a) {
        mergeSort(a, 0, a.length - 1);
        return a;
    }

    private static void mergeSort(int[] a, int l, int h) {
        if (l >= h) {
            return;
        }
        int m = l + ((h - l) >> 1);
        mergeSort(a, l, m);
        mergeSort(a, m + 1, h);
        merge(a, l, m, h);
    }

    private static void merge(int[] a, int l, int m, int h) {
        //注意数组长度
        int[] temp = new int[h - l + 1];
        int li = l;
        int ri = m + 1;
        int i = 0;

        while (li <= m && ri <= h) {
            if (a[li] <= a[ri]) {
                temp[i] = a[li];
                li++;
            } else {
                temp[i] = a[ri];
                ri++;
            }
            i++;
        }

        while (li <= m) {
            temp[i] = a[li];
            li++;
            i++;
        }
        while (ri <= h) {
            temp[i] = a[ri];
            ri++;
            i++;
        }
        System.arraycopy(temp, 0, a, 0 + l, temp.length);
    }

}
